package MST;

import pojo.Edge;

import java.util.Arrays;
import java.util.Scanner;


/**
 * <p>
 *   prime算法的部分思路与dijkstra很相似，同学们可以比较记忆
 *  本算法的核心思想也是贪心，至今还记得陈越姥姥的那句精辟总结：让一棵小树长大
 *  用贪心的思路去看待这个算法，就是贪心地选择最小的边，这样最终的树就小了，
 *  相信大家会很通透的掌握本算法
 *  时间复杂度：O(n^2)
 * </p>
 * @author 没天赋
 * @since 2025-2-28
 */
@SuppressWarnings(value = "all")
public class Prime {
    //定义最大点数
    public static final int N = (int) (1e5 + 5);
    //定义边数组,这里*2是因为无向图
    public static Edge[] edges = new Edge[N << 1];
    //存邻接表头
    public static int[] head = new int[N];
    //存点到边的距离
    public static int[] dis = new int[N];
    //记录是否访问
    public static int[] vis = new int[N];
    //点数n，边数m,下标id（记录边数）,入度u，出度v，权值w，最小生成树的总权值ans,一次贪心找到dis最小的点now
    public static int n, m, id, u, v, w,ans,now;
    public static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        n = sin();
        m = sin();
        for (int i = 0; i < m; i++) {
            u = sin();
            v = sin();
            w = sin();
            //无向图所以双边都要建立（这就是为什么边数组要开双倍N<<1）
            add(u, v, w);
            add(v, u, w);
        }
        System.out.println(prime());
    }

    /**
     * 使用Prim算法求解图的最小生成树（MST）权重
     *
     * 函数说明：
     * 1. 初始化距离数组并设置起始节点
     * 2. 通过贪心策略逐步选择当前最小边加入生成树
     * 3. 最终返回生成树总权重，若图不连通则返回-1
     *
     * @return int 最小生成树的总权重，若图不连通则返回-1
     */
    public static int prime() {
        //与dijkstra相同，这里也要初始化dis为MAX_VALUE，学习过dijkstra之后大家应该不难想到这里是为什么
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[1] = 0;
        vis[1] = 1;// 标记起始节点已加入生成树
        //这里需要提前松弛一下
        for (int i = head[1]; i != 0; i = edges[i].next) {
            int x = edges[i].to;
            dis[x] = Math.min(dis[x], edges[i].val);
        }
        // 主循环：执行n-1次节点选择（最小生成树需要包含所有n个节点,已经放入了起始节点1所以进行n-1次）
        for (int i = 1; i < n; i++) {
            int mindis = Integer.MAX_VALUE;

            // 寻找当前未访问节点中距离最小的节点
            for (int j = 1; j <= n; j++) {
                if (vis[j] == 0 && dis[j] < mindis) {
                    mindis = dis[j];
                    now = j;
                }
            }

            // 无法找到有效节点说明图不连通
            if (mindis==Integer.MAX_VALUE) return -1;
            vis[now]=1;      // 将当前节点标记为已访问
            ans+=dis[now];   // 累加生成树的总权重

            // 松弛操作：更新新加入节点的邻接边
            for (int j = head[now]; j != 0; j = edges[j].next) {
                int x = edges[j].to;
                dis[x] = Math.min(dis[x], edges[i].val);
            }
        }
        return ans;
    }

    /**
     * 增边
     *
     * @param x
     * @param y
     * @param z
     */
    public static void add(int x, int y, int z) {
        id++;
        edges[id] = new Edge(y, head[x], z);
        head[x] = id;
    }

    /**
     * 读取整数方法
     *
     * @return
     */
    public static int sin() {
        return sc.nextInt();
    }
}

/*
测试数据：
5 6
1 2 1
2 5 1
1 3 1
2 4 5
3 4 1
4 5 1
--------
4*/